package com.coolingme.algo_01_list.lrucache;

import java.util.HashMap;
import java.util.Map;

/**
 * 缓存淘汰算法
 * LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，
 * 其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
 *
 * @author wangyue
 * @date 2020/11/6 17:15
 */
public class LRUCache {

    /**
     * Map容量
     */
    private int capacity;

    /**
     * 存放node的容器，用于快速找到node
     */
    private Map<Integer, CacheNode> cacheNodeMap;

    /**
     * 头结点
     */
    private CacheNode head = new CacheNode(0, "头结点");

    /**
     * 尾节点
     */
    private CacheNode tail = new CacheNode(-1, "尾节点");

    public LRUCache(int capacity) {
        this.capacity = capacity;
        // Map初始化大小
        int initialCapacity = (int) Math.pow(2, capacity - 1);
        this.cacheNodeMap = new HashMap<>(initialCapacity);
        // 头尾相连，双向链表
        this.head.next = tail;
        this.tail.prev = head;
        System.out.println(head);
    }

    /**
     * 通过node的key获取node值
     */
    public String get(Integer key) {
        // 没有key 返回空
        if (!cacheNodeMap.containsKey(key)) {
            return null;
        }
        // 存在key，将对应的node移动到尾部
        CacheNode node = cacheNodeMap.get(key);
        // 断开node前后节点对它的链接
        node.prev.next = node.next;
        node.next.prev = node.prev;
        // 将node移动到尾部
        moveToTail(node);
        System.out.println(this.head);
        return cacheNodeMap.get(key).value;
    }

    /**
     * 向链表中存放值
     */
    public void put(Integer key, String value) {
        // 链表中有key，直接替换原值
        if (get(key) != null) {
            cacheNodeMap.get(key).value = value;
            return;
        }

        // 没有当前key
        // 链表已满,去掉最旧的数据，即head的next
        if (cacheNodeMap.size() == capacity) {
            cacheNodeMap.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }

        // 将node移动到尾部,并保存至map
        CacheNode node = new CacheNode(key, value);
        cacheNodeMap.put(key, node);
        moveToTail(node);
        System.out.println(this.head);
    }

    /**
     * 将node移动到双向链表的尾
     */
    public void moveToTail(CacheNode current) {
        // 连接current的头
        current.prev = tail.prev;
        // 连接tail的头
        tail.prev = current;
        // 连接prev的尾
        current.prev.next = current;
        // 连接current的尾
        current.next = tail;
    }

}
